package TenBasicAlgorithm;
//KMP匹配算法
import java.util.Arrays;

public class KMPDemo {
    public static void main(String[] args) {
        String s1="BBC ABCDAB ABCD ABCDABCDABDE";
        String s2="ABCDABD";
        System.out.println(KMP(s1,s2));
    }
    public static int ViolentMatching(String s1,String s2){
        char[]a1=s1.toCharArray();
        char[]a2=s2.toCharArray();
        int i=0;
        int j=0;
        while (i<a1.length&&j<a2.length){//(O(n+m))
            if(a1[i]==a2[j]){
                i++;
                j++;
            }else {
                i=i-(j-1);//自带自增效果;
                j=0;
            }
        }
        if(j==a2.length){
            return i-j;
        }
        return -1;
//        int x=-1;//(O(n*m))
//        for (int i = 0; i < a1.length; i++) {
//            if(a1[i]==a2[0]){
//                x=i;
//                for (int j = 1; j <a2.length; j++) {
//                    if(a1[i+j]!=a2[j]){
//                        x=-1;
//                        break;
//                    }
//                }
//                if(x==i){
//                    return x;
//                }
//            }
//        }
//        return -1;
    }
    public static int KMP(String s1,String s2){
        char[]a1=s1.toCharArray();
        char[]a2=s2.toCharArray();
        int[]num=KmpNext(s2);
//        int[]num={0,0,0,0,1,2,0};
        System.out.println(Arrays.toString(num));
        int i=0;
        int j=0;
        while (i<a1.length&&j<a2.length){//(O(n+m))
            if(a1[i]==a2[j]){
                i++;
                j++;
            }else {
                if(j==0){
                    i++;
                    continue;
                }
                i=(i-j)+j-num[j-1];
                j=0;
            }
        }
        if(j==a2.length){
            return i-j;
        }
        return -1;
    }
    public static int[] KmpNext(String s2){//重点有点不太理解前缀和后缀的公共部分长度
        int[] next=new int[s2.length()];
        next[0]=0;
        for(int i=1,j=0;i<s2.length();i++){
            while (j>0&&s2.charAt(i)!=s2.charAt(j)){
                j=next[j-1];
            }
            if(s2.charAt(i)==s2.charAt(j)){
                j++;
            }
            next[i]=j;
        }
        return next;
    }
}
